package com.leetcode.algs4.string;

/**
 * @author Dennis Li
 * @date 2020/7/8 20:44
 */
// 低位优先
public class LSD {
    // 统计每一个String的字符，根据字符的低位大小依次排序
    // 保证字符串最后的结果，从左到右的字符顺序都是符合的
    public static void sort(String[] a, int W) {
        int N = a.length;
        int R = 256; //ASCII码
        String[] aux = new String[N];
        for (int d = W - 1; d >= 0; d--) {
            // 计算出现的次数
            int[] count = new int[R + 1];

            for (int i = 0; i < N; i++) {
                count[a[i].charAt(d) +1]++;
            }

            for (int r = 0; r < R; r++) {
                // 将次数转化为索引
                count[r + 1] = count[r];
            }

            for (int i = 0; i < N; i++) {
                // 对应位置的count索引将会在每次赋值后自增1
                // 类似于散列的方式
                aux[count[a[i].charAt(d)]++] = a[i];
            }

            for (int i = 0; i < N; i++) {
                a[i] = aux[i];
            }
        }
    }
}
